package BinaryTree;

import java.util.ArrayList;

import java.util.List;
import java.util.Stack;

public class BinaryTree implements BinarySearchTreeInterface{

    BinaryNode root = null;
    static class BinaryNode {
        int key;
        Object value;
        BinaryNode left;
        BinaryNode right;

        public BinaryNode(int kty, Object value) {
            this.key = kty;
            this.value = value;
        }

        public BinaryNode(int key, Object value, BinaryNode left, BinaryNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    @Override
    public Object get(int key) {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        while(p != null) {
            if (p.key > key) {
                p = p.left;
            }else if (p.key < key) {
                p = p.right;
            }else {
                return p.value;
            }
        }
        return null;
    }

    @Override
    public Object min() {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        while(p.left != null) {
            p = p.left;
        }
        return p.value;
    }
    public Object min(BinaryNode node) {
        if (node == null) {
            return null;
        }
        BinaryNode p = node;
        while (p.left != null) {
            p = p.left;
        }
        return p.value;
    }

    //使用递归实现找最小关键字
    public Object minRecursion() {
        return doMin(root);
    }
    private Object doMin(BinaryNode node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            return node.value;
        }
        return doMin(node.left);
    }


    @Override
    public Object max() {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        while(p.right != null) {
            p = p.right;
        }
        return p.value;
    }
    public Object max(BinaryNode node) {
        if (node == null) {
            return null;
        }
        BinaryNode p = node;
        while (p.right != null) {
            p = p.right;
        }
        return p.value;
    }

    //使用递归实现找最大关键字
    public Object maxRecursion() {
        return doMax(root);
    }
    private Object doMax(BinaryNode node) {
        if (node == null) {
            return null;
        }
        if (node.right == null) {
            return node.value;
        }
        return doMax(node.right);
    }


    @Override
    public void put(int key, Object value) {
        if (root == null) {
            root = new BinaryNode(key,value);
            return;
        }
        BinaryNode p = root;
        BinaryNode parent = null;
        while (p != null) {
            parent = p;
            if (p.key > key) {
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            }else {
                p.value = value;
                return;
            }
        }

        //该树没有该关键字，因此需要新建节点对象
        BinaryNode newNode = new BinaryNode(key,value);
        if (newNode.key < parent.key) {
            parent.left = newNode;
        }else {
            parent.right = newNode;
        }

    }

    @Override
    public Object successor(int key) {
        if (root == null) {
            return null;
        }
        //先找到该关键字节点
        BinaryNode p = root;
        BinaryNode sParent = null;
        while (p != null) {
            if (p.key > key) {
                sParent = p;
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            }else {
                break;
            }
        }
        //没有找到关键字的情况
        if (p == null) {
            return null;
        }

        //情况一:该节点存在右子树,则该后继为右子树的最小关键字
        if (p.right != null) {
            return min(p.right);
        }

        //情况二:该节点不存在右子树，那么该后继就需要到祖宗从右向左的节点
        if (sParent == null) {
            //可能不存在后继节点,比如最大关键字的节点就没有后继节点了
            return null;
        }
        return sParent.value;
    }

    @Override
    public Object predecessor(int key) {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        BinaryNode sParent = null;
        while (p != null) {
            if (p.key > key) {
                p = p.left;
            } else if (p.key < key) {
                sParent = p;
                p = p.right;
            }else {
                break;
            }
        }
        if (p == null) {
            return null;
        }
        //情况一:存在左子树，则该前任就为左子树的最大关键字节点
        if (p.left != null) {
            return max(p.left);
        }
        //情况二:不存在左子树，则该前任为从祖宗自左向右而来的节点
        if (sParent == null) {
            return null;
        }
        return sParent.value;
    }

    @Override
    public Object delete(int key) {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        BinaryNode parent = null;
        while (p != null) {
            if (p.key > key) {
                parent = p;
                p = p.left;
            } else if (p.key < key) {
                parent = p;
                p = p.right;
            }else {
                break;
            }
        }
        //没有找到该关键字的节点
        if (p == null) {
            return null;
        }

        //情况一、二、三:只有左子树或者右子树或者都没有
        if (p.right == null) {
            shift(parent,p,p.left);
        } else if (p.left == null) {
            shift(parent,p,p.right);
        }else {
            //情况四:有左右子树
            //替换节点采用删除节点的后继节点
            //先看被删的节点与替换的节点是否为紧挨在一起
            BinaryNode s = p.right;
            BinaryNode sParent = p;
            while (s.left != null) {
                sParent = s;
                s = s.left;
            }
            if (sParent != p) {
                //说明没有紧挨在一起，则需要将替换节点的右子树进行处理
                shift(sParent,s,s.right);
                s.right = p.right;
            }
            shift(parent,p,s);
            s.left = p.left;
        }

        return p.value;
    }
    private void shift(BinaryNode parent, BinaryNode delete, BinaryNode next) {
        if (parent == null) {
            root = next;
        } else if (parent.left == delete) {
            parent.left = next;
        }else if (parent.right == delete){
            parent.right = next;
        }
    }

    //使用递归实现删除关键字节点
    public BinaryNode deleteRecursion(BinaryNode node , int key) {
        if (node == null) {
            return null;
        }
        if (node.key > key) {
            node.left = deleteRecursion(node.left,key);
            return node;
        } else if (node.key < key) {
            node.right = deleteRecursion(node.right,key);
            return node;
        }else {
            if (node.right == null) {
                return node.left;
            } else if (node.left == null) {
                return node.right;
            }else {
                BinaryNode s = node.right;
                while (s.left != null) {
                    s = s.left;
                }

                s.right = deleteRecursion(node.right,s.key);
                s.left = node.left;
                return s;
            }

        }
    }

    //找 < key 的所有 value
    public List<Object> less(int key) {
        if (root == null) {
            return null;
        }
        ArrayList<Object> result = new ArrayList<>();
        BinaryNode p = root;
        Stack<BinaryNode> stack = new Stack<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            }else {
                BinaryNode pop = stack.pop();
                if (pop.key < key) {
                    result.add(pop.value);
                }else {
                    break;
                }
                p = pop.right;
            }
        }
        return result;
    }

    //找 > key 的所有 value
    public List<Object> greater(int key) {
        if (root == null) {
            return null;
        }
        ArrayList<Object> result = new ArrayList<>();
        Stack<BinaryNode> stack = new Stack<>();
        BinaryNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            }else {
                BinaryNode pop = stack.pop();
                if (pop.key > key) {
                    result.add(pop.value);
                }
                p = pop.right;
            }
        }
        return result;
    }
    //改进思路:遍历方向进行调整，先从右子树开始，再访问根节点，最后才到左子树
    public List<Object> greater1(int key) {
        if (root == null) {
            return null;
        }
        ArrayList<Object> result = new ArrayList<>();
        Stack<BinaryNode> stack = new Stack<>();
        BinaryNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null ) {
                stack.push(p);
                p = p.right;
            }else {
                BinaryNode pop = stack.pop();
                if (pop.key > key) {
                    result.add(pop.value);
                }else {
                    break;
                }
                p = pop.left;
            }
        }
        return result;
    }


    //找到 >= k1 且 =< k2 的所有value
    public List<Object> between(int k1, int k2) {
        if (root == null) {
            return null;
        }
        ArrayList<Object> result = new ArrayList<>();
        Stack<BinaryNode> stack = new Stack<>();
        BinaryNode p = root;
        while(p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            }else {
                BinaryNode pop = stack.pop();
                if (pop.key >= k1 && pop.key <= k2) {
                    result.add(pop.value);
                } else if (pop.key > k2) {
                    break;
                }
                p = pop.right;
            }
        }
            return result;
    }

}
